<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,100分)- 冗余覆盖（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>给定两个字符串s1和s2和正整数K&#xff0c;其中s1长度为n1&#xff0c;s2长度为n2&#xff0c;在s2中选一个子串&#xff0c;满足:</p> 
<ul><li>该子串长度为n1&#43;k</li><li>该子串中包含s1中全部字母&#xff0c;</li><li>该子串每个字母出现次数不小于s1中对应的字母&#xff0c;</li></ul> 
<p>我们称s2以长度k冗余覆盖s1&#xff0c;给定s1&#xff0c;s2&#xff0c;k&#xff0c;求最左侧的s2以长度k冗余覆盖s1的子串的<strong>首个元素的下标</strong>&#xff0c;如果没有返回<strong>-1</strong>。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>输入三行&#xff0c;第一行为s1&#xff0c;第二行为s2&#xff0c;第三行为k&#xff0c;s1和s2只包含小写字母</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>最左侧的s2以长度k冗余覆盖s1的子串首个元素下标&#xff0c;如果没有返回<strong>-1。</strong></p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">ab<br /> aabcd<br /> 1</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">0</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;">无</td></tr></tbody></table> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题的难点在于如何计算s2选中子串是否能够覆盖住s1&#xff0c;即s2选中子串的中的对应字符个数都大于s1中每个字符个数。</p> 
<p>本题可以参考最小覆盖子串中统计覆盖子串字符个数的求解思路。</p> 
<p>请大家看&#xff1a;</p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/128092566?spm&#61;1001.2014.3001.5501" title="LeetCode - 76 最小覆盖子串_伏城之外的博客-CSDN博客">LeetCode - 76 最小覆盖子串_伏城之外的博客-CSDN博客</a></p> 
<p><a href="https://blog.csdn.net/qfc_128220/article/details/128062246?spm&#61;1001.2014.3001.5501" title="华为机试 - 完美走位_伏城之外的博客-CSDN博客_完美走位华为">华为机试 - 完美走位_伏城之外的博客-CSDN博客_完美走位华为</a></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 3) {
    const [s1, s2, k] &#61; lines;
    console.log(getResult(s1, s2, k - 0));
    lines.length &#61; 0;
  }
});

function getResult(s1, s2, k) {
  // 在s2中选一个子串&#xff0c;满足:该子串长度为 n1&#43;k
  const n1 &#61; s1.length;
  const n2 &#61; s2.length;
  if (n2 &lt; n1 &#43; k) return -1;

  // 统计s1中所有每个字符出现的次数到count中
  const count &#61; {};
  for (let c of s1) {
    count[c] ? count[c]&#43;&#43; : (count[c] &#61; 1);
  }

  // s1字符总数
  let total &#61; n1;

  // 滑动窗口的左边界从0开始&#xff0c;最大maxI&#xff1b;滑动窗口长度len
  const maxI &#61; n2 - n1 - k;
  const len &#61; n1 &#43; k;

  // 统计s2的0~len范围内出现的s1中字符的次数
  for (let j &#61; 0; j &lt; len; j&#43;&#43;) {
    const c &#61; s2[j];
    // 如果s2的0~len范围内的字符c&#xff0c;在count[c]存在&#xff0c;则说明c是s1内有的字符&#xff0c;此时我们需要count[c]--&#xff0c;如果自减之前&#xff0c;count[c] &gt; 0&#xff0c;则自减时&#xff0c;total也应该--,否则total不--
    if (count[c] !&#61;&#61; undefined &amp;&amp; count[c]-- &gt; 0) {
      total--;
    }

    // 如果total为0了&#xff0c;则说明在s2的0~len范围内找到了所有s1中字符
    if (total &#61;&#61;&#61; 0) {
      // 此时可以直接返回起始索引0
      return 0;
    }
  }

  // 下面是从左边界1开始的滑动窗口&#xff0c;利用差异思想&#xff0c;避免重复部分求解
  for (let i &#61; 1; i &lt;&#61; maxI; i&#43;&#43;) {
    // 滑动窗口右移一格后&#xff0c;失去了s2[i - 1]&#xff0c;得到了s2[i - 1 &#43; len]&#xff0c;其余部分不变
    const remove &#61; s2[i - 1];
    const add &#61; s2[i - 1 &#43; len];

    if (count[remove] !&#61;&#61; undefined &amp;&amp; count[remove]&#43;&#43; &gt;&#61; 0) {
      total&#43;&#43;;
    }

    if (count[add] !&#61;&#61; undefined &amp;&amp; count[add]-- &gt; 0) {
      total--;
    }

    if (total &#61;&#61;&#61; 0) {
      return i;
    }
  }

  return -1;
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<p>下面统计s1中各字符数量时&#xff0c;容器没有使用HashMap&#xff0c;因为后期获取和处理HashMap中数据时比较麻烦&#xff0c;而是利用s1中所有字符都是小写字母的特点&#xff0c;使用128长度的int数组&#xff0c;因为小写字母的ASCII码范围是97~122&#xff0c;因此可以对应到0~127的int数组的索引上。</p> 
<pre><code class="language-java">import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    String s1 &#61; sc.next();
    String s2 &#61; sc.next();
    int k &#61; sc.nextInt();

    System.out.println(getResult(s1, s2, k));
  }

  public static int getResult(String s1, String s2, int k) {
    // 在s2中选一个子串&#xff0c;满足:该子串长度为 n1&#43;k
    int n1 &#61; s1.length();
    int n2 &#61; s2.length();
    if (n2 &lt; n1 &#43; k) return -1;

    // 由于字符串s1中都是小写字母&#xff0c;因此每个字母的ASCII码范围是97~122&#xff0c;因此这里初始化128长度数组来作为统计容器
    int[] count &#61; new int[128];

    // 统计s1中所有每个字符出现的次数到count中
    for (int i &#61; 0; i &lt; n1; i&#43;&#43;) {
      int c &#61; s1.charAt(i);
      count[c]&#43;&#43;;
    }

    // s1字符总数
    int total &#61; n1;

    // 滑动窗口的左边界从0开始&#xff0c;最大maxI&#xff1b;滑动窗口长度len
    int maxI &#61; n2 - n1 - k;
    // s2子串长度
    int len &#61; n1 &#43; k;

    // 统计s2的0~len范围内出现的s1中字符的次数
    for (int j &#61; 0; j &lt; len; j&#43;&#43;) {
      int c &#61; s2.charAt(j);

      // 如果s2的0~len范围内的字符c&#xff0c;在count[c]存在&#xff0c;则说明c是s1内有的字符&#xff0c;
      // 此时我们需要count[c]--&#xff0c;如果自减之前&#xff0c;count[c] &gt; 0&#xff0c;则自减时&#xff0c;total也应该--,否则total不--
      if (count[c]-- &gt; 0) {
        total--;
      }

      // 如果total为0了&#xff0c;则说明在s2的0~len范围内找到了所有s1中字符
      if (total &#61;&#61; 0) {
        // 此时可以直接返回起始索引0
        return 0;
      }
    }

    // 下面是从左边界1开始的滑动窗口&#xff0c;利用差异思想&#xff0c;避免重复部分求解
    for (int i &#61; 1; i &lt;&#61; maxI; i&#43;&#43;) {
      // 滑动窗口右移一格后&#xff0c;失去了s2[i - 1]&#xff0c;得到了s2[i - 1 &#43; len]&#xff0c;其余部分不变
      int remove &#61; s2.charAt(i - 1);
      int add &#61; s2.charAt(i - 1 &#43; len);

      if (count[remove]&#43;&#43; &gt;&#61; 0) {
        total&#43;&#43;;
      }

      if (count[add]-- &gt; 0) {
        total--;
      }

      if (total &#61;&#61; 0) {
        return i;
      }
    }
    return -1;
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
s1 &#61; input()
s2 &#61; input()
k &#61; int(input())


# 算法入口
def getResult(s1, s2, k):
    # 在s2中选一个子串&#xff0c;满足:该子串长度为 n1&#43;k
    n1 &#61; len(s1)
    n2 &#61; len(s2)
    if n2 &lt; n1 &#43; k:
        return -1

    # 统计s1中所有每个字符出现的次数到count中
    count &#61; {}
    for c in s1:
        if count.get(c) is None:
            count[c] &#61; 1
        else:
            count[c] &#43;&#61; 1

    # s1字符总数
    total &#61; n1

    # 滑动窗口的左边界从0开始&#xff0c;最大maxI&#xff1b;滑动窗口长度len
    maxI &#61; n2 - n1 - k
    n &#61; n1 &#43; k

    # 统计s2的0~len范围内出现的s1中字符的次数
    for j in range(n):
        c &#61; s2[j]
        # 如果s2的0~len范围内的字符c&#xff0c;在count[c]存在&#xff0c;则说明c是s1内有的字符&#xff0c;此时我们需要count[c]--&#xff0c;如果自减之前&#xff0c;count[c] &gt; 0&#xff0c;则自减时&#xff0c;total也应该--,否则total不--
        if count.get(c) is not None:
            if count[c] &gt; 0:
                total -&#61; 1
            count[c] -&#61; 1

        # 如果total为0了&#xff0c;则说明在s2的0~len范围内找到了所有s1中字符
        if total &#61;&#61; 0:
            # 此时可以直接返回起始索引0
            return 0

    # 下面是从左边界1开始的滑动窗口&#xff0c;利用差异思想&#xff0c;避免重复部分求解
    for i in range(1, maxI &#43; 1):
        # 滑动窗口右移一格后&#xff0c;失去了s2[i - 1]&#xff0c;得到了s2[i - 1 &#43; len]&#xff0c;其余部分不变
        remove &#61; s2[i - 1]
        add &#61; s2[i - 1 &#43; n]

        if count.get(remove) is not None:
            if count[remove] &gt;&#61; 0:
                total &#43;&#61; 1
            count[remove] &#43;&#61; 1

        if count.get(add) is not None:
            if count[add] &gt; 0:
                total -&#61; 1
            count[add] -&#61; 1

        if total &#61;&#61; 0:
            return i

    return -1


# 调用算法
print(getResult(s1, s2, k))</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>